// 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

// 要求时间复杂度为O(n)。

#include<bits/stdc++.h>
using namespace std;

// 动态规划

// 执行用时：
// 60 ms
// , 在所有 C++ 提交中击败了
// 9.18%
// 的用户
// 内存消耗：
// 31.4 MB
// , 在所有 C++ 提交中击败了
// 5.32%
// 的用户

// 空间优化，只保留两个临时数据就够了
// 时间复杂度O(n),无优化思路


class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // 0:不包括当前节点
        // 1:包括当前节点
        vector<vector<int>> res(nums.size(),vector<int>(2,INT_MIN));
        res[0][1] = nums[0];
        for(int i=1;i<nums.size();++i){
            res[i][0] = max(res[i-1][0],res[i-1][1]);
            res[i][1] = max(nums[i],res[i-1][1]+nums[i]);
        }
        return max(res[res.size()-1][0],res[res.size()-1][1]);
    }
};